#include <ctype.h>

#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <iostream>
#include <map>
#include <set>
#include <string>
#include <vector>

using namespace std;

// started at 10:48
enum SquareType {
  NORMAL = 0,
  LETTER_DOUBLE = 1,
  LETTER_TRIPLE = 2,
  WORD_DOUBLE = 3,
  WORD_TRIPLE = 4,
};

char PrettyChar(char c) {
  return c == '{' ? '*' : toupper(c);
}

struct Play {
  int score;
  string word;
  string letters_used;
  int row;
  int col;
  enum Dir {
    VERTICAL = 0,
    HORIZONTAL,
  };
  Dir dir;

  Play() : score(-1), row(-1), col(-1) { }
};

ostream& operator<<(ostream& o, const Play& p) {
  o << "Score: " << p.score << " with: ";
  for (int i = 0; i < int(p.word.size()); ++i) o << PrettyChar(p.word[i]);
  o << ", " << (p.dir == Play::VERTICAL ? "vertically" : "horizontally")
    << " at row " << p.row << " and col " << p.col << " using letters:";
  for (int i = 0; i < int(p.letters_used.size()); ++i) {
    o << " " << PrettyChar(p.letters_used[i]);
  }
  return o;
}

Play FindBestPlay(
    vector<string>& board,
    const vector<vector<SquareType> >& square_type,
    string letters,
    vector<int> points,
    const set<string>& dict) {
  const clock_t c0 = clock();
  const int h = board.size();
  const int w = board[0].size();
  Play play;
  vector<int> char_count(27, 0);
  for (int i = 0; i < int(letters.size()); ++i) {
    char_count[letters[i] - 'a']++;
  }
  bool empty_board = true;
  for (int i = 0; i < h; ++i) for (int j = 0; j < w; ++j) {
    empty_board &= board[i][j] == ' ';
  }
  for (int i = 0; i < h; ++i) {
    for (int j = 0; j < w; ++j) {
      for (int dir = 0; dir < 2; ++dir) {
        if (empty_board && dir == Play::VERTICAL) continue;
        const int incr_i = dir == 0 ? 1 : 0;
        const int incr_j = dir == 0 ? 0 : 1;
        if (empty_board) {
          if (i > h/2 || j > w/2) continue;
          if (incr_i == 0 && i != h/2) continue;
          if (incr_j == 0 && j != w/2) continue;
        }
        // The word must *start* there.
        if (i - incr_i >= 0 && j - incr_j >= 0
            && board[i - incr_i][j - incr_j] != ' ') {
          continue;
        }
        // The word must be long enough to touch a non-empty square, and cover
        // at least one empty square.
        bool has_empty_square = false;
        bool touches_letter = false;
        int min_len = 0;
        if (!empty_board) {
          while (!has_empty_square || !touches_letter) {
            ++min_len;
            const int ii = i + (min_len - 1)*incr_i;
            const int jj = j + (min_len - 1)*incr_j;
            if (ii >= h || jj >= w) break;
            if (board[ii][jj] == ' ') has_empty_square = true;
            else touches_letter = true;
            touches_letter |= ii - incr_j >= 0 && board[ii - incr_j][jj] != ' ';
            touches_letter |= ii + incr_j < h && board[ii + incr_j][jj] != ' ';
            touches_letter |= jj - incr_i >= 0 && board[ii][jj - incr_i] != ' ';
            touches_letter |= jj + incr_i < h && board[ii][jj + incr_i] != ' ';
          }
          if (!has_empty_square || !touches_letter) continue;
        }
        // Precompute acceptable lengths for the word.
        vector<bool> acceptable_length(1024, false);
        for (int len = min_len; len <= 15; ++len) {
          if (i + len*incr_i >= h) continue;
          if (j + len*incr_j >= w) continue;
          if (empty_board &&
              (i + len*incr_i < h/2 || j + len*incr_j < w/2)) {
            continue;
          }
          // The word must *end* at its end.
          if (i + len*incr_i < h && j + len*incr_j < h &&
              board[i + len*incr_i][j + len*incr_j] != ' ') {
            continue;
          }
          acceptable_length[len] = true;
        }
        for (set<string>::const_iterator it = dict.begin();
             it != dict.end(); ++it) {
          const string& word = *it;
          if (!acceptable_length[word.size()]) continue;
          int word_multiplier = 1;
          int score = 0;
          int word_score = 0;
          string letters_used;
          int k = 0;
          vector<int> cc = char_count;
          for (int ii = i, jj = j; k < int(word.size()); ++k, ii+=incr_i, jj+=incr_j) {
            const char c = word[k];
            if (c < 'a' || c > 'z') break;
            int letter_points = points[c - 'a'];
            if (board[ii][jj] != ' ') {
              if (board[ii][jj] != c) break;
              word_score += letter_points;
              continue;
            }
            int multiplier = 1;
            if (cc[c - 'a']-- <= 0) {
              if (cc[26]-- <= 0) break;
              letters_used += '{';
              letter_points = 0;
            } else {
              letters_used += c;
            }
            switch (square_type[ii][jj]) {
              case LETTER_DOUBLE: letter_points *= 2; break;
              case LETTER_TRIPLE: letter_points *= 3; break;
              case WORD_DOUBLE: multiplier = 2; break;
              case WORD_TRIPLE: multiplier = 3; break;
              case NORMAL: break;
            }
            word_multiplier *= multiplier;
            word_score += letter_points;

            // Look at the orthogonally-formed word.
            string orth_word(1, c);
            int orth_word_score = letter_points;
            for (int iii = ii - incr_j, jjj = jj - incr_i;
                 iii >= 0 && iii < h && jjj >= 0 && jjj < w
                     && board[iii][jjj] != ' ';
                 iii -= incr_j, jjj -= incr_i) {
              orth_word += board[iii][jjj];
              orth_word_score += points[board[iii][jjj] - 'a'];
            }
            reverse(orth_word.begin(), orth_word.end());
            for (int iii = ii + incr_j, jjj = jj + incr_i;
                 iii >= 0 && iii < h && jjj >= 0 && jjj < w
                     && board[iii][jjj] != ' ';
                 iii += incr_j, jjj += incr_i) {
              orth_word += board[iii][jjj];
              orth_word_score += points[board[iii][jjj] - 'a'];
            }
            if (orth_word.size() > 1) {
              if (dict.count(orth_word) == 0) break;
              score += orth_word_score * multiplier;
            }
          }
          if (k != int(word.size()) || letters_used.empty()) continue;
          score += word_score * word_multiplier;
          if (letters_used.size() == 7) score += 50;  // SCRABBLE!
          if (score > play.score) {
            play.score = score;
            play.row = i;
            play.col = j;
            play.dir = static_cast<Play::Dir>(dir);
            play.word = word;
            play.letters_used = letters_used;
          }
        }
      }
    }
  }
  cout << "Finished in " << double(clock() - c0) / CLOCKS_PER_SEC << "s.\n";
  return play;
}

// Finished at 11:31

// Taken from http://en.wikipedia.org/wiki/Scrabble_letter_distributions .
int kNumberAndPoints[] = {
  9, 1,   // A
  2, 3,   // B
  2, 3,   // C
  3, 2,   // D
  15, 1,  // E
  2, 4,   // F
  2, 2,   // G
  2, 4,   // H
  8, 1,   // I
  1, 8,   // J
  1, 10,  // K
  5, 1,   // L
  3, 2,   // M
  6, 1,   // N
  6, 1,   // O
  2, 3,   // P
  1, 8,   // Q
  6, 1,   // R
  6, 1,   // S
  6, 1,   // T
  6, 1,   // U
  2, 4,   // V
  1, 10,  // W
  1, 10,  // X
  1, 10,  // Y
  1, 10,  // Z
  2, 0,   // *
};

const char kNormalBash[] = "\033[0m";
const char kGreyBash[] = "\033[47m";
const char kRedBash[] = "\033[41m";
const char kPurpleBash[] = "\033[45m";
const char kBlueBash[] = "\033[44m";
const char kCyanBash[] = "\033[46m";

int main(int argc, char** argv) {
  srandom(time(0));
  cout << "Reading dictionary...";
  set<string> dict;
  {
    FILE* f = fopen("/home/viger/games/scrabble_words_fr.txt", "r");
    char buff[80];
    while (fgets(buff, 64, f)) {
      if (buff[0] < 'a' && buff[0] > 'z') continue;
      if (strchr(buff, '\'') != NULL) continue;
      char* newline = strchr(buff, '\n');
      if (newline) *newline = '\0';
      dict.insert(buff);
    }
    fclose(f);
  }
  cout << " Read " << dict.size() << " words.\n";

  // Interactive board entry.
  vector<string> board;
  const bool pause = argc > 1 && string(argv[1]) == "-p";
  if (argc > 1 && string(argv[1]) == "-i") {
    cout << "Enter the 15x15 board, line by line (use spaces for empty squares)\n";
    for (int i = 0; i < 15; ++i) {
      char buff[80];
      if (fgets(buff, 80, stdin) == 0) {
        cout << "Error when reading the existing board; exiting.\n";
        return -1;
      }
      string line = buff;
      if (line[line.size()-1] == '\n') line = line.substr(0, line.size() - 1);
      if (line.size() < 15) line += string(15 - line.size(), ' ');
      if (line.size() > 15) line = line.substr(0, 15);
      board.push_back(line);
    }
  } else {
    cout << "-i flag not used: starting with an empty board.\n";
    board.assign(15, string(15, ' '));
  }

  // Define special squares.
  vector<vector<SquareType> > sq(15, vector<SquareType>(15, NORMAL));
  for (int i = 0; i <= 14; i += 7) for (int j = 0; j <= 14; j += 7) {
    sq[i][j] = WORD_TRIPLE;
  }
  for (int i = 1; i < 14; i++) sq[i][i] = sq[14-i][i] = WORD_DOUBLE;
  for (int i = 1; i <= 13; i += 4) for (int j = 1; j <= 13; j += 4) {
    if ((i != 1 && i != 13) || (j != 1 && j != 13)) sq[i][j] = LETTER_TRIPLE;
  }
  int kDoubleLetterX[] = { 0, 2, 3, 3, 6, 6, 7 };
  int kDoubleLetterY[] = { 3, 6, 0, 7, 2, 6, 3 };
  for (int k = 0; k < 7; ++k) {
    for (int q = 0; q < 4; ++q) {
      int x = kDoubleLetterX[k];
      int y = kDoubleLetterY[k];
      if (q % 2) x = 14 - x;
      if (q >= 2) y = 14 - y;
      sq[x][y] = LETTER_DOUBLE;
    }
  }

  // Initialize points and letter pool.
  string all_letters;
  vector<int> points;
  for (int i = 0; i < 27; ++i) {
    points.push_back(kNumberAndPoints[2*i + 1]);
    all_letters += string(kNumberAndPoints[2*i], 'a' + i);
  }
  random_shuffle(all_letters.begin(), all_letters.end());

  // Main play loop.
  string letters;
  int total_score = 0;
  for (;;) {
    if (argc > 1 && string(argv[1]) == "-i") {
      cout << "Enter the letters you have: ";
      cin >> letters;
      for (int i = 0; i < letters.size(); ++i) {
        if (letters[i] == '?' || letters[i] == '*') letters[i] = '{';
      }
    } else {
      // Draw some letters.
      while (letters.size() < 7 && !all_letters.empty()) {
        letters.push_back(*all_letters.rbegin());
        all_letters.erase(all_letters.end() - 1);
      }
    }

    // Pretty-print current board and letters...
    cout << "Here is the board:\n\n";
    for (int i = 0; i < 15; ++i) {
      for (int j = 0; j < 15; ++j) {
        switch (sq[i][j]) {
          case NORMAL: cout << kGreyBash; break;
          case LETTER_DOUBLE: cout << kCyanBash; break;
          case LETTER_TRIPLE: cout << kBlueBash; break;
          case WORD_DOUBLE: cout << kPurpleBash; break;
          case WORD_TRIPLE: cout << kRedBash; break;
        }
        cout << PrettyChar(board[i][j]);
      }
      cout << kNormalBash;
      if (i == 2) {
        // Draw your letters.
        cout << "   ";
        for (int i = 0; i < int(letters.size()); ++i) {
          cout << "  " << PrettyChar(letters[i]);
        }
      } else if (i == 3) {
        // Draw the points of your letters.
        cout << "   ";
        for (int i = 0; i < int(letters.size()); ++i) {
          char pp[80];
          sprintf(pp, "%2d", points[letters[i] - 'a']);
          cout << " " << pp;
        }
      }
      cout << "\n";
    }

    if (all_letters.empty() && letters.empty()) {
      cout << "Finished! Total score: " << total_score << "\n";
      break;
    }
    if (pause) {
      cout << "\nPress a key to start the solver.\n";
      cin.get();
    }
    cout << "Solving...\n";
    Play play = FindBestPlay(board, sq, letters, points, dict);
    if (play.word.empty()) {
      cout << "No possible word. Stopping...\n";
      break;
    }
    cout << play << "\n";

    sort(letters.begin(), letters.end());
    sort(play.letters_used.begin(), play.letters_used.end());
    int kept = 0;
    for (int i = 0, j = 0; i < int(letters.size()); ) {
      if (j >= int(play.letters_used.size())
          || letters[i] < play.letters_used[j]) {
        letters[kept++] = letters[i++];
        continue;
      }
      if (letters[i] == play.letters_used[j]) i++;
      j++;
      // I'm adding this funky comment.
    }
    letters.erase(letters.begin() + kept, letters.end());
    const int incr_i = play.dir == Play::VERTICAL ? 1 : 0;
    const int incr_j = play.dir == Play::HORIZONTAL ? 1 : 0;
    for (int k = 0; k < int(play.word.size()); ++k) {
      board[play.row + k * incr_i][play.col + k * incr_j] = play.word[k];
    }
    total_score += play.score;
    cout << "Total score so far: " << total_score << "\n";
    if (pause) {
      cout << "Now press a key to go to the next turn.\n";
      cin.get();
    }
  }
}
